package name.huzhenbo.java.algorithm.graph;

/**
 * The algorigthm was found by Floyd.
 * <p/>
 * If  d[i][k] + d[k][j] < d[i][j], then new d[i][j] = d[i][k] + d[k][j]
 * <p/>
 * 4 level loop
 */
class FloydShortestPath {
    private Graph graph;
    private int[][] distances;

    // middlePoints[i][j] represents the middle points from i to j
    private boolean[][][] middlePoints;

    public FloydShortestPath(Graph graph) {
        this.graph = graph;
        distances = new int[graph.vertexNum()][graph.vertexNum()];
        middlePoints = new boolean[graph.vertexNum()][graph.vertexNum()][graph.vertexNum()];
        execute();
    }

    private void execute() {
        for (int i = 0; i < graph.vertexNum(); i++)
            for (int j = 0; j < graph.vertexNum(); j++) {
                distances[i][j] = graph.weight(i, j);
                if (distances[i][j] != -1) {
                    middlePoints[i][j][i] = true;
                    middlePoints[i][j][j] = true;
                }
            }

        for (int i = 0; i < graph.vertexNum(); i++) {
            pathThrough(i);
        }
    }

    /**
     * @param k: the intermediate point
     */
    private void pathThrough(int k) {
        for (int i = 0; i < graph.vertexNum(); i++) {
            for (int j = 0; j < graph.vertexNum(); j++) {
                if (distances[i][k] != -1 && distances[k][j] != -1) {
                    if (distances[i][j] == -1 || distances[i][j] > distances[i][k] + distances[k][j]) {
                        distances[i][j] = distances[i][k] + distances[k][j];
                        for (int t = 0; t < graph.vertexNum(); t++) {
                            // if t is the middle point of i to k or k to j, then it is the middle point of i to j.
                            middlePoints[i][j][t] = middlePoints[i][k][t] || middlePoints[k][j][t];
                        }
                    }
                }
            }
        }
    }

    public int distance(int start, int end) {
        return distances[start][end];
    }

    public void path(int start, int end) {
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < graph.vertexNum(); t++) {
            if (middlePoints[start][end][t]) {
                sb.append(t);
                sb.append(", ");
            }
        }
        System.out.println(sb);
    }
}
